import {
  TCompareFunc,
} from '../utils/tools';
import {
  tools,
  constant,
} from '../utils';

const { defaultCompare, swap, } = tools;
const { LESS_THAN, } = constant;

export class MinHeap {
  protected compareFunc: TCompareFunc;
  protected heap: any[];

  public constructor(elements?: any[], compareFunc?: TCompareFunc,) {
    this.compareFunc = compareFunc ?? defaultCompare;
    this.heap = [0];

    if (elements) {
      for (let val of elements) {
        this.insert(val);
      }
    }
  }

  public insert(key: any) {
    let count = this.heap[0];
    
    this.heap.push(key);
    this.heap[0] = ++count;
    
    if (count > 1) {
      this.moveUp();
    }
  }

  public getSize() {
    return this.heap[0];
  }

  public isEmpty() {
    return this.getSize() === 0;
  }

  public findMinimum() {
    return this.isEmpty() ? undefined : this.heap[1];
  }

  public outputMin() {
    let result: any;
    if (this.isEmpty()) {
      result = undefined;
    } else if (this.getSize() === 1) {
      result = this.heap[1];
      this.heap.pop();
      this.heap[0]--;
    } else {
      swap(this.heap, 1, this.heap[0]);
      result = this.heap.pop();
      this.heap[0]--;
      this.moveDown();
    }
    return result;
  }

  /**
   * Swap the position of parent with the position of child when the value of cihld is less than the value of parent.
   * Move up the item that insert to the heap recently.
   */
  protected moveUp() {
    let cIndex = this.heap[0];
    let pIndex = this.getIndexParent(cIndex);
    let pValue = this.heap[pIndex];
    let cValue = this.heap[cIndex];

    while (pIndex > 0 && this.compareFunc(cValue, pValue) === LESS_THAN) {
      swap(this.heap, pIndex, cIndex);
      cIndex = pIndex;
      pIndex = this.getIndexParent(cIndex);
      pValue = this.heap[pIndex];
      cValue = this.heap[cIndex];
    }
  }

  protected moveDown() {
    const size = this.getSize();
    let index = 1;
    let lIndex = this.getIndexLeft(index);
    let rIndex = this.getIndexRight(index);
    let iValue = this.heap[index];
    let lValue = this.heap[lIndex];
    let rValue = this.heap[rIndex];

    while(
      (lIndex <= size && this.compareFunc(iValue, lValue) > LESS_THAN)
      ||
      (rIndex <= size && this.compareFunc(iValue, rValue) > LESS_THAN)
    ) {
      if (this.compareFunc(lValue, rValue) === LESS_THAN) {
        swap(this.heap, index, lIndex);
        index = lIndex;
      } else {
        swap(this.heap, index, rIndex);
        index = rIndex;
      }

      lIndex = this.getIndexLeft(index);
      rIndex = this.getIndexRight(index);
      iValue = this.heap[index];
      lValue = this.heap[lIndex];
      rValue = this.heap[rIndex];
    }
  }

  protected getIndexRight(index: number) {
    return 2 * index + 1;
  }

  protected getIndexLeft(index: number) {
    return 2 * index;
  }

  protected getIndexParent(index: number) {
    return Math.floor(index / 2);
  }
}
